package com.rui.shangXueTang.kruskal.crusk;

import java.util.Arrays;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : KruskalAlg
 * @createTime : [2022/2/19 20:42]
 * @description : [描述该类的功能]
 */

public class KruskalAlg {
    public static void main(String[] args) {
        Graph graph = new Graph();
        int[][] arr = new int[7][7];

        for(int i = 0 ; i < 7 ; i++){
            for(int j = 0 ; j < 7 ; j++){
                if(i == j){
                    arr[i][j] = 0;
                }else {
                    arr[j][i] = Integer.MAX_VALUE;
                }
            }
        }

        arr[0][1] = 7;
        arr[0][3] = 5;
        arr[1][2] = 8;
        arr[1][3] = 9;
        arr[2][4] = 5;
        arr[3][4] = 15;
        arr[4][5] = 8;
        arr[4][6] = 9;
        arr[5][6] = 11;

        graph.array = arr;
        int k = 0;
        Edge[] edge = new Edge[11];

        for(int i = 0 ; i <edge.length ; i++){
            Edge edge1 = new Edge();
            edge[i] = edge1;
        }

        for(int i = 0 ; i < 6 ; i++){
            for(int j = 0 ; j < 7 ; j++){
                if(arr[i][j] != Integer.MAX_VALUE){
                    edge[k].begin = i;
                    edge[k].end = j;
                    edge[k].weight = arr[i][j];
                    k++;
                }
            }
        }

        graph.edges = edge;
        Arrays.sort(edge);
        kruskal(graph);
    }

    /**
     * 是否会构成回路
     * @param target 新加节点
     * @param parent
     * @return
     */
    public static int findParentRoot(int target, int[] parent) {
        while(parent[target] > 0){
            target = parent[target];
        }
        return target;
    }

    public static void kruskal(Graph graph){
        Edge[] edges = graph.edges;
        int[][] arr = graph.array;
        int[] parent = new int[7];
        for (Edge edge : edges) {
            int begin = findParentRoot(edge.begin, parent);
            int end = findParentRoot(edge.end, parent);
            if (begin != end) {
                System.out.printf("(%d,%d)---->%d%n", begin, end, edge.weight);
                parent[begin] = end;
            }
        }
    }
}
